import collections
class Solution(object):
    def findRedundantConnection(self, edges):
        """
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        d = collections.defaultdict(int)
        e = collections.defaultdict(set)
        for edge in edges:
            e[edge[0]].add(edge[1])
            e[edge[1]].add(edge[0])
            d[edge[0]] += 1
            d[edge[1]] += 1
        now_set = set()
        for key in d:
            if d[key] == 1:
                now_set.add(key)
        while now_set:
            next_set = set()
            for node in now_set:
                for next_node in e[node]:
                    d[next_node] -= 1
                    e[next_node].remove(node)
                    if d[next_node] == 1:
                        next_set.add(next_node)
            now_set = next_set
        for edge in edges[::-1]:
            if d[edge[0]] == 2 and d[edge[1]] == 2:
                return edge


